package com.cuz.daileetcode;

import com.sun.xml.internal.bind.v2.model.core.ID;

public class Day44 {

    /**
     * 括号序列是否合法
     * <p>
     * 一个完整的括号字符串定义规则如下:
     * ①空字符串是完整的。
     * ②如果s是完整的字符串，那么(s)也是完整的。
     * ③如果s和t是完整的字符串，将它们连接起来形成的st也是完整的。
     * 例如，"(()())"，""和"(())()"是完整的括号字符串，
     * "())("，"()(”和“)"是不完整的括号字符串。
     * <p>
     */
    static class LegalBracketSequence {
        /****
         * 使用有限个常量判断是否是有效的括号序列
         *
         *
         * @param str 需要判断的字符串
         * @return 是否合法的括号序列
         */
        static boolean isLegalBracketSequence(String str) {
            if (str == null || "".equals(str)) {
                return true;
            }
            int len = str.length();
            //偶数 101010 最后以为必定为0  & 0000001 为0 奇数&00001为1
            //奇数个字符 必定不是有效的
            if ((len & 1) != 0) {
                return false;
            }
            char[] charArray = str.toCharArray();
            //遍历字符串，此变量记录左括号和右括号个数之差
            int leftBracketRightDiff = 0;
            for (char temp : charArray) {
                //如果左括号
                if (temp == '(') {
                    leftBracketRightDiff++;
                } else {
                    //如果右括号
                    leftBracketRightDiff--;
                }
                //如果此时 小于0代表右括号再这一瞬间是大于左括号的 说明已经不是合法的序列了
                if (leftBracketRightDiff < 0) {
                    return false;
                }
            }
            //最后左括号必须和右括号一样多
            return leftBracketRightDiff == 0;
        }

        /**
         * 牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,
         * 将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。
         *
         * @param str 字符串
         * @return 需要添加的个数
         */
        static int lessBracketAddToMakeSequenceLegal(String str) {
            if (str == null || "".equals(str)) {
                return 0;
            }
            char[] charArray = str.toCharArray();
            //如果某一瞬间 右括号个数大于左括号
            // 那么我们让右括号++代表我们需要添加多少个左括号让序列继续合法
            int rightMoreThanLeft = 0;
            //遍历字符串，此变量记录左括号和右括号个数之差
            //和上述代码不同的是
            //这个值如果一旦小于0 我们会让 rightMoreThanLeft++
            //然后让leftBracketRightDiff 恢复零， leftBracketRightDiff只统计左括号多余右括号的个数
            //rightMoreThanLeft 统计 多少个右括号在左括号之前出现且无法配对
            int leftBracketRightDiff = 0;
            for (char temp : charArray) {
                //如果左括号
                if (temp == '(') {
                    leftBracketRightDiff++;
                } else {
                    //如果右括号
                    leftBracketRightDiff--;
                }
                //如果此时 小于0代表右括号再这一瞬间是大于左括号的 说明已经不是合法的序列了
                if (leftBracketRightDiff == -1) {
                    rightMoreThanLeft++;
                }
            }
            return rightMoreThanLeft + leftBracketRightDiff;
        }
    }

    /**
     * 给定一个非负整数n，代表二叉树的节点个数。返回能形成多少种不同的二叉树结构
     */
    static class BinaryTreeKind {
        /***
         * 递归
         */
        static int solution1(int n) {
            if (n < 0) {
                return 0;
            }
            if (n <= 1) {
                return 1;
            }
            if (n == 2) {
                return 2;
            }
            int sum = 0;
            for (int leftTreeNodeNum = 0; leftTreeNodeNum <= n - 1; leftTreeNodeNum++) {
                sum += solution1(leftTreeNodeNum) * solution1(n - 1 - leftTreeNodeNum);
            }
            return sum;
        }


        /***
         * 动态规划
         */
        static int solution2(int n) {
            if (n < 0) {
                return 0;
            }
            if (n <= 1) {
                return 1;
            }
            int[] dp = new int[n + 1];
            dp[0] = 1;
            for (int nodeNum = 1; nodeNum < n + 1; nodeNum++) {
                //左侧节点个数为leftNodeNumAdd1-1 右侧为 nodeNum-leftNodeNumAdd1，剩下的一个给头节点
                for (int leftNodeNumAdd1 = 1; leftNodeNumAdd1 < nodeNum + 1; leftNodeNumAdd1++) {
                    dp[nodeNum] += dp[leftNodeNumAdd1 - 1] * dp[nodeNum - leftNodeNumAdd1];
                }
            }
            return dp[n];
        }

        public static void main(String[] args) {
            for (int index = 51; index < 60; index++) {
                try {
                    System.out.println(index);
                    int j = solution2(index);
                    System.out.println(j);
                    int i = solution1(index);
                    System.out.println(i);
                    if (i != j) {
                        System.out.println(index);
                        System.out.println("递归：" + i);
                        System.out.println("dp：" + j);
                        break;
                    }
                    System.out.println(index+"--ok");
                } catch (Exception e) {
                    System.out.println("eeee_" + index);
                    e.printStackTrace();
                    throw e;
                }

            }
        }
    }

}
